//
// Created by Administrator on 2021/6/6.
//
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int findMaxForm(vector<string> &strs, int m, int n) {
        if (strs.empty()) return 0;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (auto &x:strs) {
            vector<int> &&zeroOnes = getZerosOnes(x);
            int zeros = zeroOnes[0], ones = zeroOnes[1];
            for (int i = m; i >= zeros; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }

    vector<int> getZerosOnes(string &str) {
        vector<int> zerosOnes(2);
        for (auto &x:str) {
            zerosOnes[x - '0']++;
        }
        return zerosOnes;
    }

};

int main() {
    vector<string> str{"10", "0001", "111001", "1", "0"};
    Solution sol;
    cout << sol.findMaxForm(str, 5, 3) << endl;
    return 0;
}